class Solution
{
public:
    int fib(int n)
    {
        if (n < 2)
        {
            return n;
        }

        vector<vector<int>> coff{ {1, 1}, {0, 1} };
        vector<vector<int>> ret = matrix_pow(coff, n - 1);
        return ret[0][0];
    }

    vector<vector<int>> matrix_pow(vector<vector<int>> a, int n)
    {
        vector<vector<int>> ret{ {1, 0}, {0, 1} };          // 单位矩阵
        while (n > 0)
        {
            if (n & 1)
            {
                ret = matrix_multipy(ret, a);
            }
            n >>= 1;
            a = matrix_multipy(a, a);
        }
        return ret;
    }


    vector<vector<int>> matrix_multipy(const vector<vector<int>>& a, const vector<vector<int>>& b)
    {
        vector<vector<int>> ret{ {0, 0}, {0, 0} };

        for (size_t cntRow = 0; cntRow < 2; cntRow++)
        {
            for (size_t cntCol = 0; cntCol < 2; cntCol++)
            {
                ret[cntRow][cntCol] = a[cntRow][0] * b[0][cntCol] + a[cntRow][1] * b[1][cntCol];
            }
        }

        return ret;
    }
};